package search

/**
二分查找，针对的是一个有序的数据集合，
查找思想有点类似分治思想 —— 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
二分查找的时间复杂度是 O(logn)
使用二分查找需要一个前提，那就是有序数据，换言之，二分查找适用于变动不是很频繁的静态序列集，如果序列集变动很频繁，经常进行插入删除操作，那么就要不断维护这个序列集的排序，这个成本也很高，
对于这种动态数据集，要同时保证更新（包含插入和删除）和查询的高效，通常有两种方案，一种是哈希表，一种是树结构，比如 Redis 底层就是基于哈希表的，而 MySQL 底层则是基于 B+ 树
*/
func BinarySearch(nums []int, num int) int {
	return binarySearch(nums, num, 0, len(nums)-1)
}
func binarySearch(nums []int, num int, low int, high int) int {
	// 递归终止条件
	if low > high {
		return -1
	}
	// 通过中间元素进行二分查找
	mid := (low + high) / 2
	// 递归查找
	if num > nums[mid] {
		// 如果待查找数据大于中间元素，则在右区间查找
		return binarySearch(nums, num, mid+1, high)
	} else if num < nums[mid] {
		// 如果待查找数据小于中间元素，则在左区间查找
		return binarySearch(nums, num, low, mid-1)
	} else {
		// 找到了，返回索引值
		return mid
	}
}
